package leetcode每日一题.leetcode20212;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 1. 问题描述
 *      给定一个范围在1≤a[i]≤n(n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
 *      找到所有在 [1,n]范围之间没有出现在数组中的数字。
 *      您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
 *
 * 2. 算法分析
 *      1. 实现HashSet进行去除重复元素，然后进行1到n数字的扫描  时间和空间都是O(n)
 *
 *      2. 优化空间的算法实现
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q013_找到所有数组中消失的数字 {

    public List<Integer> findDisappearedNumbers1(int[] nums) {
        int n = nums.length;
        HashSet<Integer> set = new HashSet<>();
        for(int x : nums) {
            set.add(x);
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            if(!set.contains(i)) {
                res.add(i);
            }
        }
        return res;
    }

    /**
     * 分析下面代码的具体思路：
     *      下面的代码并没有使用额外的空间，而是使用nums本身作为hash表
     *      由于题目给出的nums数组中的元素范围在1<=x<=n之间，其中n为数
     *      组的长度，我们需要找到缺省的数字，完整的数字为1,2,3.....,n
     *      即数组nums的第i个位置应该为元素i+1(排序之后)，注意到这一点
     *      我们可以使用n之外的数字来记录当前已经出现在nums中的元素，扫
     *      描整个数组，假设当前扫描到的元素为x，则x在排序之后的位置为数
     *      组中第x-1的位置上，所以我们让nums[x-1] + n,这样如果是已经
     *      出现的元素在操作完上述之后，其对应位置上的元素应该大于n，剩下
     *      没有大于的都是缺省的
     *      此外还需要注意一点：我们并不能直接修改nums[x-1]+n,因为位置x-1
     *      处的值之前可能已经修改过了，一旦修改之后x-1肯定是超出可数组的索
     *      引范围，所以在修改之前我们需要对x-1进行取模运算，将其拉回到数组
     *      的正确索引范围之内
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for(int x : nums) {
            x = (x-1) % n;
            nums[x] += n;
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] <= n) {
                res.add(i+1);
            }
        }
        return res;
    }
}
